# 给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。
#
#  岛屿总是被水包围，并且每座岛屿只能由水平方向或竖直方向上相邻的陆地连接形成。
#
#  此外，你可以假设该网格的四条边均被水包围。
#
#
#
#  示例 1:
#
#  输入:
# [
# ['1','1','1','1','0'],
# ['1','1','0','1','0'],
# ['1','1','0','0','0'],
# ['0','0','0','0','0']
# ]
# 输出: 1
#
#
#  示例 2:
#
#  输入:
# [
# ['1','1','0','0','0'],
# ['1','1','0','0','0'],
# ['0','0','1','0','0'],
# ['0','0','0','1','1']
# ]
# 输出: 3
# 解释: 每座岛屿只能由水平和/或竖直方向上相邻的陆地连接而成。
#
#  Related Topics 深度优先搜索 广度优先搜索 并查集
#  👍 747 👎 0


# leetcode submit region begin(Prohibit modification and deletion)
from typing import List


class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:

        if len(grid) == 0:
            return 0
        m, n = len(grid), len(grid[0])

        def dfs(grid, x, y):
            if x < 0 or y < 0 or x >= m or y >= n or grid[x][y] == '0' or grid[x][y] == '2':
                return

            if grid[x][y] == '1':
                grid[x][y] = '2'

                dfs(grid, x + 1, y)
                dfs(grid, x - 1, y)
                dfs(grid, x, y + 1)
                dfs(grid, x, y - 1)

        count = 0
        for i in range(0, m):
            for j in range(0, n):
                if grid[i][j] == '1':
                    dfs(grid, i, j)
                    count += 1

        return count


# leetcode submit region end(Prohibit modification and deletion)

print(Solution().numIslands(
    [["1", "1", "1", "1", "0"],
     ["1", "1", "0", "1", "0"],
     ["1", "1", "0", "0", "0"],
     ["0", "0", "0", "0", "0"]]))
